home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / kernel / timer / timerQueue.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-19  |  14.6 KB  |  557 lines
  1. /* 
  2.  * timerQueue.c --
  3.  *
  4.  *    Routines to handle interrupts from the timer chip.
  5.  *
  6.  *      The timer call back routine is called at every callback timer
  7.  *      interrupt. The callback timer is used to enable various modules of
  8.  *      the kernel to have routines called at a particular time in the
  9.  *      future.  For example, to run the "clock" paging algorithm once a
  10.  *      second, to see if a Fs_Select call has timed-out, etc.  The timer
  11.  *      queue can only be used by kernel modules because it is assumed
  12.  *      that the routines to be called exist in the system segment.  The
  13.  *      routines to be called are maintained on the timer queue.  The
  14.  *      callback timer is active only when the timer queue is not empty.
  15.  *
  16.  *
  17.  * Copyright 1986, 1988 Regents of the University of California
  18.  * Permission to use, copy, modify, and distribute this
  19.  * software and its documentation for any purpose and without
  20.  * fee is hereby granted, provided that the above copyright
  21.  * notice appear in all copies.  The University of California
  22.  * makes no representations about the suitability of this
  23.  * software for any purpose.  It is provided "as is" without
  24.  * express or implied warranty.
  25.  */
  26.  
  27. #ifndef lint
  28. static char rcsid[] = "$Header: /cdrom/src/kernel/Cvsroot/kernel/timer/timerQueue.c,v 9.7 92/06/01 14:54:46 kupfer Exp $ SPRITE (Berkeley)";
  29. #endif not lint
  30.  
  31. #include <sprite.h>
  32. #include <timer.h>
  33. #include <timerInt.h>
  34. #include <sys.h>
  35. #include <sync.h>
  36. #include <sched.h>
  37. #include <list.h>
  38. #include <vm.h>
  39. #include <dev.h>
  40. #include <stdio.h>
  41. #include <bstring.h>
  42.  
  43.  
  44. /*
  45.  * Procedures internal to this file
  46.  */
  47.  
  48. void TimerDumpElement _ARGS_((Timer_QueueElement *timerPtr));
  49.  
  50.  
  51.  
  52. /* DATA STRUCTURES */
  53.  
  54. /*
  55.  *  The timer queue is a linked list of routines that need to be called at
  56.  *  certain times. TimerQueueList points to the head structure for the queue.
  57.  *
  58.  * >>>>>>>>>>>>>>>>>>>
  59.  * N.B. For debugging purposes, timerQueueList is global
  60.  *      so it can be accessed by routines outside this module.
  61.  * <<<<<<<<<<<<<<<<<<<
  62.  */ 
  63.  
  64. /* static */ List_Links    *timerQueueList;
  65.  
  66. /*
  67.  * The timer module mutex semaphore.  
  68.  */
  69.  
  70. Sync_Semaphore timerMutex;
  71.  
  72. /*
  73.  *  Debugging routine and data.
  74.  */
  75.  
  76. #ifdef DEBUG
  77. #define SIZE 500
  78. static unsigned char array[SIZE+1];
  79. static int count = 0;
  80. #endif DEBUG
  81.  
  82. /*
  83.  * Instrumentation for counting how many times the routines get called.
  84.  */
  85.  
  86. Timer_Statistics timer_Statistics;
  87.  
  88.  
  89.  
  90. /*
  91.  *----------------------------------------------------------------------
  92.  *
  93.  * Timer_Init --
  94.  *
  95.  *    Initializes the data structures necessary to manage the timer
  96.  *    queue of procedures.
  97.  *
  98.  * Results:
  99.  *     None.
  100.  *
  101.  * Side effects:
  102.  *     The timer queue structure is created and initialized.
  103.  *
  104.  *----------------------------------------------------------------------
  105.  */
  106.  
  107. void
  108. Timer_Init()
  109. {
  110.     static    Boolean    initialized    = FALSE;
  111.  
  112.     Sync_SemInitDynamic(&timerMutex,"Timer:timerMutex");
  113.  
  114.     if (initialized) {
  115.     printf("Timer_Init: Timer module initialized more that once!\n");
  116.     }
  117.     initialized = TRUE;
  118.  
  119.     TimerTicksInit();
  120.  
  121.     bzero((Address) &timer_Statistics, sizeof(timer_Statistics));
  122.  
  123.     timerQueueList = (List_Links *) Vm_BootAlloc(sizeof(List_Links));
  124.     List_Init(timerQueueList);
  125.  
  126.     /*
  127.      * Initialized the time of day clock.
  128.      */
  129.     TimerClock_Init();
  130.     Timer_TimerInit(TIMER_CALLBACK_TIMER);
  131.     Timer_TimerStart(TIMER_CALLBACK_TIMER);
  132. }
  133.  
  134.  
  135.  
  136. /*
  137.  *----------------------------------------------------------------------
  138.  *
  139.  *  Timer_CallBack --
  140.  *
  141.  *      This routine is called at every call back timer interrupt. 
  142.  *      It calls routines on the timer queue. 
  143.  *
  144.  *  Results:
  145.  *    None.
  146.  *
  147.  *  Side Effects:
  148.  *    Routines on the timer queue may cause side effects.
  149.  *
  150.  *----------------------------------------------------------------------
  151.  */
  152.  
  153. void
  154. Timer_CallBack(interval, time)
  155.     unsigned int interval;  /* Number of ticks since last invocation. */
  156.     Time   time;            /* Interval as time. */
  157. {
  158.     register List_Links    *readyPtr;    /* Ptr to TQE that's ready
  159.                          * to be called. */
  160.     Time            timeOfDay;    /* Best guess at tod. */
  161.     Timer_Ticks        currentSystemTimeTk;
  162.  
  163.     /*
  164.      *  The callback timer has expired. This means at least the first
  165.      *  routine on the timer queue is ready to be called.  Go through
  166.      *  the queue and call all routines that are scheduled to be
  167.      *  called. Since the queue is ordered by time, we can quit looking 
  168.      *  when we find the first routine that does not need to be called.
  169.      */
  170.  
  171. #ifdef GATHER_STAT
  172.     timer_Statistics.callback++;
  173. #endif
  174.  
  175.     MASTER_LOCK(&timer_ClockMutex);
  176.     Time_Add(timer_UniversalApprox, time, &timer_UniversalApprox);
  177.     timeOfDay = timer_UniversalApprox;
  178.     MASTER_UNLOCK(&timer_ClockMutex);
  179.  
  180.     Sched_GatherProcessInfo(interval);
  181.     Dev_GatherDiskStats();
  182.  
  183.     MASTER_LOCK(&timerMutex);
  184.     if (!List_IsEmpty(timerQueueList)) {
  185.         Timer_GetCurrentTicks(¤tSystemTimeTk);
  186.         while (!List_IsEmpty(timerQueueList)) {
  187.         readyPtr = List_First(timerQueueList); 
  188.         if(Timer_TickGT(((Timer_QueueElement *)readyPtr)->time, 
  189.                   currentSystemTimeTk)) {
  190.             break;
  191.         } else {
  192.  
  193.             /*
  194.              *  First remove the item before calling it so the routine 
  195.              *  can call Timer_ScheduleRoutine to reschedule itself on 
  196.              *  the timer queue and not mess up the pointers on the 
  197.              *  queue.
  198.              */
  199.  
  200.             List_Remove(readyPtr);
  201.  
  202.             /*
  203.              *  Now call the routine.  It is interrupt time and 
  204.              *  the routine must do as little as possible.  The 
  205.              *  routine is passed the time it was scheduled to 
  206.              *  be called at and a client-specified argument.
  207.              * 
  208.              *  We release the timerMutex during the call backs to
  209.              *    prevent the many deadlocks that can occur on a 
  210.              *    multiprocessor.
  211.              */
  212.  
  213. #define  ELEMENTPTR ((Timer_QueueElement *) readyPtr)
  214.  
  215.             if (ELEMENTPTR->routine == 0) {
  216.             panic("Timer_ServiceInterrupt: t.q.e. routine == 0\n");
  217.             } else {
  218.             void        (*routine) _ARGS_((Timer_Ticks timeTicks,
  219.                               ClientData  clientData));
  220.             Timer_Ticks timeTk;
  221.             ClientData  clientData;
  222.  
  223.             ELEMENTPTR->processed = TRUE;
  224.             routine = ELEMENTPTR->routine;
  225.             timeTk = ELEMENTPTR->time;
  226.             clientData = ELEMENTPTR->clientData;
  227.             MASTER_UNLOCK(&timerMutex);
  228.             (routine) (timeTk, clientData);
  229.             MASTER_LOCK(&timerMutex);
  230.             }
  231.         }
  232.         }
  233. #undef  ELEMENTPTR
  234.  
  235.  
  236.     } 
  237.     MASTER_UNLOCK(&timerMutex);
  238.     
  239. }
  240.  
  241.  
  242. /*
  243.  *----------------------------------------------------------------------
  244.  *
  245.  * Timer_ScheduleRoutine --
  246.  *
  247.  *    Schedules a routine to be called at a certain time by adding 
  248.  *    it to the timer queue. A routine is specified using a
  249.  *    Timer_QueueElement structure, which is described in timer.h.
  250.  *
  251.  *    When the client routine is called at its scheduled time, it is 
  252.  *    passed two parameters:
  253.  *     a) the time it is scheduled to be called at, and
  254.  *     b) uninterpreted data.
  255.  *    Hence the routine should be declared as:
  256.  *
  257.  *        void
  258.  *        ExampleRoutine(time, data)
  259.  *        Timer_Ticks time;
  260.  *        ClientData data;
  261.  *        {}
  262.  *
  263.  *
  264.  *    The time a routine should be called at can be specified in two
  265.  *    ways: an absolute time or an interval. For example, to have 
  266.  *    ExampleRoutine called in 1 hour, the timer queue element would 
  267.  *    be setup as:
  268.  *        Timer_QueueElement    element;
  269.  *
  270.  *        element.routine    = ExampleRoutine;
  271.  *        element.clientData    = (ClientData) 0;
  272.  *        element.interval    = timer_IntOneHour;
  273.  *        Timer_ScheduleRoutine(&element, TRUE);
  274.  *
  275.  *    The 2nd argument (TRUE) to Timer_ScheduleRoutine means the routine
  276.  *    will be called at the interval + the current time.
  277.  *
  278.  *      Once ExampleRoutine is called, it can schedule itself to be
  279.  *      called again using Timer_ScheduleRoutine().   
  280.  *
  281.  *        Timer_ScheduleRoutine(&element, TRUE);
  282.  *
  283.  *    The 2nd argument again means schedule the routine relative to the
  284.  *    current time. Since we still want ExampleRoutine to be called in
  285.  *    an hour, we don't have to change the interval field in the timer
  286.  *    queue element.
  287.  *      Obviously, the timer queue element has to be accessible 
  288.  *    to ExampleRoutine.
  289.  *
  290.  *    If we want ExampleRoutine to be called at a specific time, say
  291.  *    March 1, 1986, the time field in the t.q. element must be set:
  292.  *
  293.  *        element.routine    = ExampleRoutine;
  294.  *        element.clientData    = (ClientData) 0;
  295.  *        element.time    = march1;
  296.  *        Timer_ScheduleRoutine(&element, FALSE);
  297.  *
  298.  *    (Assume march1 has the appropriate value for the date 3/1/86.)
  299.  *
  300.  * Results:
  301.  *    None.
  302.  *
  303.  * Side effects:
  304.  *    The timer queue element is added to the timer queue.
  305.  *
  306.  *----------------------------------------------------------------------
  307.  */
  308.  
  309. void
  310. Timer_ScheduleRoutine(newElementPtr, interval)
  311.     register    Timer_QueueElement *newElementPtr; /* routine to be added */
  312.     Boolean    interval;    /* TRUE if schedule relative to current time. */
  313. {
  314.     register List_Links     *itemPtr;
  315.     Boolean inserted;        /* TRUE if added to Q in FORALL loop. */
  316.  
  317.     MASTER_LOCK(&timerMutex); 
  318.     /*
  319.      *  Go through the timer queue and insert the new routine.  The queue
  320.      *  is ordered by the time field in the element.  The sooner the
  321.      *  routine needs to be called, the closer it is to the front of the
  322.      *  queue.  The new routine will not be added to the queue inside the
  323.      *  FOR loop if its scheduled time is after all elements in the queue
  324.      *  or the queue is empty.  It will be added after the last element in
  325.      *  the queue.
  326.      */
  327.  
  328.     inserted = FALSE;  /* assume new element not inserted inside FOR loop.*/
  329.  
  330. #ifdef GATHER_STAT
  331.     timer_Statistics.schedule++;
  332. #endif
  333.  
  334.     /*
  335.      * Safety check.
  336.      */
  337.     if (newElementPtr->routine == 0) {
  338.     panic("Timer_ScheduleRoutine: bad address for t.q.e. routine.\n");
  339.     }
  340.  
  341.     /* 
  342.      *  Reset the processed flag. It is used by the client to see if 
  343.      *  the routine is being called from the timer queue. This flag is
  344.      *  necessary because the client passes in the timer queue element
  345.      *  and it may need to examine the element to determine its status.
  346.      */
  347.     newElementPtr->processed = FALSE;
  348.  
  349.     /*
  350.      * Convert the interval into an absolute time by adding the 
  351.      * interval to the current time.
  352.      */
  353.     if (interval) {
  354.     Timer_Ticks currentTime;
  355.     Timer_GetCurrentTicks(¤tTime);
  356.     Timer_AddIntervalToTicks(currentTime, newElementPtr->interval,
  357.                        &(newElementPtr->time));
  358.     }
  359.  
  360.     List_InitElement((List_Links *) newElementPtr);
  361.  
  362.     LIST_FORALL(timerQueueList, itemPtr) {
  363.  
  364.        if (Timer_TickLT(newElementPtr->time, 
  365.        ((Timer_QueueElement *)itemPtr)->time)) {
  366.         List_Insert((List_Links *) newElementPtr, LIST_BEFORE(itemPtr));
  367.         inserted = TRUE;
  368.         break;
  369.     }
  370.     }
  371.  
  372.     if (!inserted) {
  373.     List_Insert((List_Links *) newElementPtr, LIST_ATREAR(timerQueueList));
  374.     }
  375.     MASTER_UNLOCK(&timerMutex); 
  376. }
  377.  
  378.  
  379. /*
  380.  *----------------------------------------------------------------------
  381.  *
  382.  * Timer_DescheduleRoutine --
  383.  *
  384.  *    Deschedules a routine to be called at a certain time by removing 
  385.  *    it from the timer queue.
  386.  *
  387.  *    Note that Timer_DescheduleRoutine does NOT guarantee that the 
  388.  *    routine to be descheduled will not be called, only that the 
  389.  *    routine will not be on the timer queue when Timer_DescheduleRoutine 
  390.  *    returns.
  391.  *
  392.  *    If Timer_DescheduleRoutine is able to obtain the timer mutex before
  393.  *    the timer interrupts, the routine will be removed from the
  394.  *    timer queue before the interrupt handler has a chance to call it.
  395.  *    If the interrupt handler is able to obtain the timer mutex before
  396.  *    Timer_DescheduleRoutine, then the interrupt handler will remove and 
  397.  *    call the routine before Timer_DescheduleRoutine has a chance 
  398.  *    to remove it.
  399.  *
  400.  * Results:
  401.  *    TRUE if the element was removed, FALSE if it was already gone.
  402.  *
  403.  * Side effects:
  404.  *    The timer queue structure is updated. 
  405.  *
  406.  *----------------------------------------------------------------------
  407.  */
  408.  
  409. Boolean
  410. Timer_DescheduleRoutine(elementPtr)
  411.     register Timer_QueueElement *elementPtr;    /* routine to be removed */
  412. {
  413.     register List_Links     *itemPtr;
  414.  
  415. #ifdef GATHER_STAT
  416.     timer_Statistics.desched++;
  417. #endif
  418.     Boolean foundIt = FALSE;
  419.  
  420.     /*
  421.      *  Go through the timer queue and remove the routine.  
  422.      */
  423.  
  424.     MASTER_LOCK(&timerMutex); 
  425.  
  426.     LIST_FORALL(timerQueueList, itemPtr) {
  427.  
  428.     if ((List_Links *) elementPtr == itemPtr) {
  429.         List_Remove(itemPtr);
  430.         foundIt = TRUE;
  431.         break;
  432.     }
  433.     }
  434.  
  435.     MASTER_UNLOCK(&timerMutex);
  436.     return(foundIt);
  437. }
  438.  
  439. /*
  440.  *----------------------------------------------------------------------
  441.  *
  442.  * Timer_DumpQueue --
  443.  *
  444.  *    Output the timer queue on the display.
  445.  *
  446.  * Results:
  447.  *    None.
  448.  *
  449.  * Side effects:
  450.  *    Output is written to the display.
  451.  *
  452.  *----------------------------------------------------------------------
  453.  */
  454.  
  455. /*ARGSUSED*/
  456. void
  457. Timer_DumpQueue(data)
  458.     ClientData    data;    /* Not used. */
  459. {
  460.     Timer_Ticks    ticks;
  461.     Time    time;
  462.     List_Links *itemPtr;
  463.  
  464.     Timer_GetCurrentTicks(&ticks);
  465.     Timer_TicksToTime(ticks, &time);
  466.     printf("Now: %d.%06u sec\n", time.seconds, time.microseconds);
  467.  
  468.     if (List_IsEmpty(timerQueueList)) {
  469.     printf("\nList is empty.\n");
  470.     } else {
  471.     printf("\n");
  472.  
  473.     MASTER_LOCK(&timerMutex); 
  474.  
  475.     LIST_FORALL(timerQueueList, itemPtr) {
  476.         TimerDumpElement((Timer_QueueElement *) itemPtr);
  477.     }
  478.  
  479.     MASTER_UNLOCK(&timerMutex); 
  480.  
  481.     }
  482. }
  483.  
  484. /*
  485.  *----------------------------------------------------------------------
  486.  *
  487.  * TimerDumpElement --
  488.  *
  489.  *    Output the more important parts of a Timer_QueueElement on the display.
  490.  *
  491.  * Results:
  492.  *    None.
  493.  *
  494.  * Side effects:
  495.  *    Output is written to the display.
  496.  *
  497.  *----------------------------------------------------------------------
  498.  */
  499.  
  500. void
  501. TimerDumpElement(timerPtr)
  502.     Timer_QueueElement *timerPtr;
  503. {
  504.     Time      time;
  505.  
  506.     Timer_TicksToTime(timerPtr->time, &time);
  507.  
  508.     printf("(*0x%x)(0x%x) @ %d.%06u\n",
  509.         (Address) timerPtr->routine, 
  510.         (Address) timerPtr->clientData,
  511.         time.seconds, time.microseconds);
  512. }
  513.  
  514. /*
  515.  *----------------------------------------------------------------------
  516.  *
  517.  * Timer_DumpStats --
  518.  *
  519.  *    Initializes and prints the timer module statistics.
  520.  *
  521.  * Results:
  522.  *    None.
  523.  *
  524.  * Side effects:
  525.  *    Output is written to the display.
  526.  *
  527.  *----------------------------------------------------------------------
  528.  */
  529. void
  530. Timer_DumpStats(arg)
  531.     ClientData    arg;
  532. {
  533.     static   Timer_Ticks    start;
  534.     static   Timer_Ticks    end;
  535.     Timer_Ticks    diff;
  536.     Time      time;
  537.  
  538.     if (arg ==  (ClientData) 's') {
  539.     Timer_GetCurrentTicks(&start);
  540.     bzero((Address) &timer_Statistics,sizeof(timer_Statistics));
  541.     } else {
  542.     Timer_GetCurrentTicks(&end);
  543.     Timer_SubtractTicks(end, start, &diff);
  544.     Timer_TicksToTime(diff, &time);
  545.  
  546.     printf("\n%d.%06d cb %d prof %d spur %d; Sched %d Res %d Des %d\n",
  547.         time.seconds, time.microseconds,
  548.         timer_Statistics.callback,
  549.         timer_Statistics.profile,
  550.         timer_Statistics.spurious,
  551.         timer_Statistics.schedule,
  552.         timer_Statistics.resched,
  553.         timer_Statistics.desched
  554.     );
  555.     }
  556. }
  557.